// 局部反转一个链表

import { ListNode } from '../types'

/**
 * 真题描述：
 * 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
 *
 * 示例:
 * 输入: 1->2->3->4->5->NULL, m = 2, n = 4
 * 输出: 1->4->3->2->5->NULL
 *
 * 说明:
 * 1 ≤ m ≤ n ≤ 链表长度。
 */

const reserveBetween = function reverseBetween(
	head: ListNode,
	m: number,
	n: number
): ListNode {
	const dummy = new ListNode()
	dummy.next = head

	let p = dummy, // 游标, 用于遍历记录节点位置
		leftHead, // 记录第 m 个节点前面的节点
		start // m,n 区间开始的节点

	let pre, // 用于反转的前一个节点
		cur // 用于反转的当前节点

	for (let i = 0; i < m - 1; i++) {
		p = p.next!
	}

	leftHead = p
	start = leftHead.next

	pre = leftHead.next
	cur = pre.next

	for (let i = m; i < n; i++) {
		const next = cur.next
		cur.next = pre
		pre = cur
		cur = next
	}

	start.next = cur
	leftHead.next = pre

	return dummy.next
}
